package codingforgreat.class49;

import java.util.HashSet;

public class Problem_0489_RobotRoomCleaner {
    // 不要提交这个接口的内容
    interface Robot {
         boolean move();

         void turnLeft();

         void turnRight();

         void clean();
    }
    /**
     * 算法思路： 当前在（x，y） 清理，加入列表
     * 向四个方向尝试，若能够到达则执行递归 这个递归最终会跑完所有格子
     * 像四个方向尝试后需要偏转回原方向
     *
     * 0 0 0       0 0 0    0 R 0    0 1 R
     * 0 R 0 -》   0 1 0 -》0 1 0 -》0 1 0  -》
     * 0 0 0       0 0 0    0 0 0    0 0 0
     * */

    public static void cleanRoom(Robot robot) {
        clean(robot, 0, 0, 0, new HashSet<>());
    }
    private static final int[][] ds = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };
    public static void clean(Robot robot,int x,int y,int d,HashSet<String> visited){
        robot.clean();
        visited.add(x + "_" + y);
        for(int i = 0; i < 4;i++){
            //方向
            //d = 0  nd：0 1 2 3 ...
            int nd = (i + d) % 4;
            int nx = ds[nd][0] + x;
            int ny = ds[nd][1] + y;
            if(!visited.contains(nx + "_" + ny) && robot.move()){
                clean(robot,nx,ny,nd,visited);
            }
            robot.turnRight();
        }
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }
}
